#include <iostream>
#include <string>

using namespace std;

template<typename T>
class LinkedList {
private:
    typedef struct Node {
        T e;
        struct Node *next;

        Node(T e, Node *next) : e(e), next(next) {}
    } Node;
    Node *list;
    int length{};
public:
    /**
     * 初始化一个空的链表
     */
    LinkedList() {
        this->list = new Node(0, nullptr);
    }

    /**
     * 初始化一个带元素的链表
     * @param arr
     * @param len
     */
    LinkedList(T *arr, int len) {
        this->list = new Node(0, nullptr);
        Node *ptr = this->list;
        while (ptr->next != nullptr) {
            ptr = ptr->next;
        }
        for (int i = 0; i < len; i++) {
            Node *pNew = new Node(arr[i], nullptr);
            ptr->next = pNew;
            ptr = ptr->next;
            this->length++;
        }
    }

    /**
     * 输出链表中所有元素
     */
    void printList() {
        cout << "LinkedList:";
        Node *ptr = this->list;
        while (ptr->next != nullptr) {
            ptr = ptr->next;
            cout << ptr->e << " ";
        }
        cout << endl;
    }

    /**
     * 在链表指定位置插入元素
     * @param e 待插入元素
     * @param index 插入位置索引
     * @return 0 成功,其它 失败
     */
    int insert(T e, int index) {
        if (index < 0)index = 0;
        if (index > this->length) index = this->length;
        Node *newNode = new Node(e, nullptr);
        Node *p = this->list;
        for (int i = 0; i < index && p->next != nullptr; i++, p = p->next);
        newNode->next = p->next;
        p->next = newNode;
        this->length++;
        return 0;
    }

    /**
     * 删除指定位置的元素
     * @param index 待删除元素下标
     * @return 删除的元素
     * @note 下标越界会导致删除对应方向的第一个节点数据
     */
    T remove(int index) {
        if (index < 0)index = 0;
        if (index >= this->length)index = this->length - 1;
        Node *p = this->list;
        for (int i = 0; i < index && p->next != nullptr; i++, p = p->next);
        Node *delNode = p->next;
        p->next = delNode->next;
        T e = delNode->e;
        delete delNode;
        this->length--;
        return e;
    }

    /**
     * 返回元素索引
     * @param e
     * @return -1 未找到该元素否则返回对用下标
     */
    int getIndex(T e) {
        int i = 0;
        Node *p = this->list;
        while (i < this->length && p->e != e) {
            i++;
            p = p->next;
        }
        if (i == this->length) {
            return -1;
        }
        return i - 1;
    }

    /**
     * 获取指定位置的元素
     * @param index
     * @return 对应位置的元素
     * @note 下标越界会导致删除对应方向的第一个节点数据
     */
    T getElem(int index) {
        int i = 0;
        Node *p = this->list;
        while (i < index - 1 && p->next != nullptr) {
            i++;
            p = p->next;
        }
        return p->e;
    }

    /**
     * 替换指定位置的元素值
     * @param index 元素索引
     * @param e 新元素
     * @note 下标越界会导致删除对应方向的第一个节点数据
     */
    void replace(int index, T e) {
        if (index < 0)index = 0;
        if (index >= this->length)index = this->length - 1;
        int i = 0;
        Node *p = this->list;
        while (i < index && p->next != nullptr) {
            i++;
            p = p->next;
        }
        p->e = e;
    }

    /**
     * 删除所有值为e的结点,并释放其空间
     * @param e
     */
    void removeAllByElem(T e) {
        Node *p = this->list;
        while (p->next != nullptr) {
            if (p->next->e == e) {
                Node *delNode = p->next;
                p->next = delNode->next;
                delete delNode;
                this->length--;
            } else {
                p = p->next;
            }
        }
    }

    /**
     * 删除一个最小值结点
     */
    void removeMin() {
        Node *pMinPri = nullptr;
        Node *p = this->list;
        while (p->next != nullptr) {
            if (pMinPri == nullptr || p->next->e < pMinPri->next->e) {
                pMinPri = p;
            }
            p = p->next;
        }
        p = pMinPri;
        pMinPri = pMinPri->next;
        p->next = pMinPri->next;
        delete pMinPri;
        this->length--;
    }

    /**
     * 删除表中所有处于给定的两个值之间的元素
     * @param min
     * @param max
     */
    void removeRangeElem(T min, T max) {
        if (min > max)return;
        Node *p = this->list;
        while (p->next != nullptr) {
            if (p->next->e <= max && p->next->e >= min) {
                Node *delNode = p->next;
                p->next = delNode->next;
                delete delNode;
                this->length--;
            } else {
                p = p->next;
            }
        }
    }

    /**
     * 删除重复的元素
     * @note 必须是递增有序的单链表
     */
    void removeRepetition() {
        Node *p = this->list;
        while (p->next != nullptr) {
            if (p->next->next != nullptr && p->next->next->e == p->next->e) {
                Node *delNode = p->next->next;
                p->next->next = delNode->next;
                delete delNode;
            } else {
                p = p->next;
            }
        }
    }

    LinkedList<T> mergeLinkedList(LinkedList<T> l) {
        return nullptr;
    }
};

int main() {
}